GATE CSE 2013
Q31.
The line graph L(G) of a simple graph G is defined as follows: There is exactly one vertex v(e) in L(G) for each edge e in G. For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.Q32.
In the following truth table, V = 1 if and only if the input is valid. What function does the truth table represent?Q33.
The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have atmost two source operands and one destination operand. Assume that all variables are dead after this code segment. c = a + b; d = c * a; e = c + a; x = c * c; if (x > a) { y = a * a; } else { d = d * d; e = e * e; } Suppose the instruction set architecture of the processor has only two registers. The only allowed compiler optimization is code motion, which moves statements from one place to another while preserving correctness. What is the minimum number of spills to memory in the compiled code?Q34.
The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have atmost two source operands and one destination operand. Assume that all variables are dead after this code segment. c = a + b; d = c * a; e = c + a; x = c * c; if (x > a) { y = a * a; } else { d = d * d; e = e * e; } What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any optimization other than optimizing register allocationQ35.
Which one of the following does NOT equal \begin{bmatrix} 1 & x&x^{2} \\ 1& y & y^{2}\\ 1&z & z^{2} \end{bmatrix}?Q36.
A RAM chip has a capacity of 1024 words of 8 bits each (1K x 8). The number of 2 x 4 decoders with enable line needed to construct a 16K x 16 RAM from 1K x 8 RAM isQ37.
Consider the DFA A given below. Which of the following are FALSE? 1. Complement of L(A) is context-free. 2. L(A) = L((11*0+0) (0+1)*0*1*) 3. For the language accepted by A, A is the minimal DFA. 4. A accepts all strings over {0, 1} of length at least 2.Q38.
Using public key cryptography, X adds a digital signature \sigma to message M, encrypts \lt M, \sigma \gt, and sends it to Y, where it is decrypted. Which one of the following sequences of keys is used for the operations?Q39.
The smallest integer that can be represented by an 8-bit number in 2's complement form isQ40.
Relation R has eight attributes ABCDEFGH. Fields of R contain only atomic values. F=\{CH\rightarrow G, A\rightarrow BC,B\rightarrow CFH,E\rightarrow A,F\rightarrow EG\} is a set of functional dependencies (FDs) so that F^{+} is exactly the set of FDs that hold for R. How many candidate keys does the relation R have?